/*
 * @lc app=leetcode.cn id=779 lang=typescript
 *
 * [779] 第K个语法符号
 */

// @lc code=start
function kthGrammar(n: number, k: number): number {
  if (n === 1) return 0;
  return (k & 1) ^ 1 ^ kthGrammar(n - 1, (k + 1) >> 1);
}
// @lc code=end
